#include <iostream>
#include <algorithm>
#include <vector> 
#include <cmath>
using namespace std;
#define int long long
#define double long double
//#define mod 998244353
//
//int n, m, d;
//string s[2010];
//int dp[2010][2010][2];
//int sdp[2010][2010][2];
//
//int getsum(int x, int y1, int y2, int f) {
//	int res = sdp[x][y2][f];
//	if (y1) res -= sdp[x][y1 - 1][f];
//	return res;
//}
//
//
//int get(int i, int j, int f) {
//	if (s[i][j] != 'X')return 0;
//	int res = 0;
//	if (i == n - 1)res++;
//
//	if (f) {
//		res += getsum(i, max((int)0, j - d), min(m - 1, j + d), 0);
//		res -= dp[i][j][0];
//	}
//
//	if (i < n - 1) {
//		res += getsum(i + 1, max((int)0, j - d + 1), min(m - 1, j + d - 1), 1);
//	}
//	
//	return res % mod;
//}
//
//void solve() {
//	cin >> n >> m >> d;
//	for (int i = 0; i < n; i++) {
//		cin >> s[i];
//	}
//	for (int i = n - 1; i >= 0; i--) {
//		for (int f = 0; f <=1; f++) {
//			for (int j = 0; j < m; j++) {
//				sdp[i][j][f] = dp[i][j][f] = get(i, j, f);
//			}
//			for (int j = 1; j < m; j++) {
//				sdp[i][j][f] += sdp[i][j - 1][f];
//			}
//		}
//	}
//
//	int ans = 0;
//	for (int i = 0; i < m; i++) {
//		ans += dp[0][i][1];
//	}
//
//	cout << ans % mod << '\n';
//
//}
//
//int a[200005], n;
//int f[200005];
//#define eps 1e-9
//
//bool notsmall(int a, int f1, int b, int f2) {
//	double lga = log10(1.0 * a), lgb = log10(1.0 * b);
//	double lglga = log10(lga), lglgb = log10(lgb);
//	double lg2 = log10(2.0);
//	
//	return (f1 * lg2 + lglga + eps >= f2 * lg2 + lglgb);
//}
//
//
//void solve() {
//	cin >> n;
//	for (int i = 1; i <= n; i++) {
//		cin >> a[i];
//	}
//	for (int i = 1; i <= n; i++) f[i] = 0;
//	int ans = 0;
//	for (int i = 2; i <= n; i++) {
//		if (notsmall(a[i], 0, a[i - 1], f[i - 1]))continue;
//		if (a[i] == 1) {
//			ans = -1;
//			break;
//		}
//		int l = 1, r = 1e10, m;
//		while (l < r) {
//			int m = (l + r) >> 1;
//			if (notsmall(a[i], m, a[i - 1], f[i - 1])) {
//				f[i] = m;
//				r = m;
//			}
//			else
//				l = m + 1;
//		}
//		ans += f[i];
//	}
//	cout << ans << '\n';
//}
//
//signed main() {
//	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//	int t;
//	cin >> t;
//	while (t--) {
//		solve();
//	}
//
//	return 0;
//}